import java.util.Comparator;
import java.util.PriorityQueue;

public class TestHeap {

    //前k个最小值
    public int[] smallesk(int[] arr, int k) {
        //创建最小根
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //将数组中的元素放到堆中
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);//放到堆中
            int usedSize = 0;
        }
        //将弹出的元素放到数组中
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();//弹出
        }
        return tmp;
    }

    //堆中的前k个最大或者最小的数据
    //Top-K问题
    public static int[] smallesks(int[] arr, int k) {
        if (arr == null || k == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //将数组元素放到堆中
        for (int i = 0; i < arr.length ; i++) {
            if (minHeap.size() < k) {
                //直接
                minHeap.offer(arr[i]);
            }else {
                //当前数组元素时arr[i]
                int val = minHeap.peek();//得到此时的堆顶元素
                if (val > arr[i]) {
                    //此时i下标的元素小于堆顶元素 - 出堆顶元素
                    minHeap.poll();//弹出较大的堆顶元素
                    minHeap.offer(arr[i]);//插入现在较小的i小标的数据
                }
            }
        }
        //循环结束 - n-k个元素遍历完成
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();//弹出
        }
        return tmp;
    }

    public boolean isEmpty() {
        return
    }
    //堆排序
    public void heapSort() {

    }

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] arr = {1, 5, 2 ,9, 8, 20, 18};
        testHeap.smallesk(arr, 3);//找出最小的3个数
    }
}
